﻿using System;
using Algoritmia.DataStructures.Lists;
using Algoritmia.Utils;

namespace Algoritmia.Problems.SequenceComparison.EditDistance
{
    public class EditDistanceComputer<T>
    {
        private readonly EqualityComparison<T> _equalityComparison;

        public EditDistanceComputer(EqualityComparison<T> equalityComparison = null)
        {
            _equalityComparison = AlgoritmiaFactory.GetDefaultEqualityComparison(equalityComparison);
        }

        public int Distance(IList<T> x, IList<T> y)
        {
            var D = new int[x.Count + 1][];
            for(int i = 0; i <= x.Count; i++)
            {
                D[i] = new int[y.Count+1];
            }
            D[0][0] = 0;
            for(int i = 1; i <= x.Count; i++)
            {
                D[i][0] = D[i - 1][0] + 1;
            }
            for(int j = 1; j <= y.Count; j++)
            {
                D[0][j] = D[0][j - 1] + 1;
                for(int i = 1; i <= x.Count; i++)
                {
                    D[i][j] = Math.Min(D[i - 1][j] + 1, D[i][j - 1] + 1);
                    D[i][j] = Math.Min(D[i][j], D[i - 1][j - 1] + (_equalityComparison(x[i - 1], y[j - 1]) ? 0 : 1));
                }
            }
            return D[x.Count][y.Count];
        }
    }

    public class EditDistanceComputer : EditDistanceComputer<char>
    {
        public int Distance(string x, string y)
        {
            return base.Distance(x.ToAlgoritmiaList(), y.ToAlgoritmiaList());
        }
    }
}
